package algorithm;

import java.util.HashMap;
import java.util.Map;
import java.util.Stack;

/**
 * @author MaGuangQi
 * @description 有效的括号
 * 给定一个字符串,包含{},[],().判断该字符串是否有效
 * 有效的条件是 1.左括号必须用相同类型的右括号闭合。
 * 2.左括号必须以正确的顺序闭合
 * <p>
 * 例如{} true {[()]} true {]{}(} false
 * https://leetcode-cn.com/problems/valid-parentheses/
 * <p>
 * s="{[()]}" s={[[()}}
 * @date 2020-06-15 14:28
 **/
public class CheckBrackets {
    /**
     * 解法一: 使用字符串替换,既然括号是成对的, 那我们把字符串中成对的括号
     * 每次都给替换了.最后判断字符串是否为空即可
     */
    public static boolean isValid(String s) {
        if (s == null && "".equals(s)) {
            return false;
        } else {
            int length;
            int repLength;
            String replaceAfter;
            do {
                //替换前长度
                length = s.length();
                 replaceAfter = s.replace("()", "")
                        .replace("[]", "")
                        .replace("{}", "");
                repLength=replaceAfter.length();
                s=replaceAfter;
            } while (length !=repLength&&length!=0);

            if ("".equals(replaceAfter)) {
                return true;
            }else{
                return false;
            }
        }
    }
    /**
    *解法二: 使用栈
     * 遇到左括号暂时压栈,遇到右括号,和栈顶元素比较是否是一对,如果是一对
     * 继续,不是直接return false;
    */
    public static boolean isValid2(String s) {
        Map<Character, Character> map = new HashMap<Character, Character>(3);
        map.put('}', '{');
        map.put(']', '[');
        map.put(')', '(');
        Stack<Character> stack = new Stack<Character>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            //右括号,和栈顶元素做判断
            if (map.containsKey(c)) {
                Character topElement=stack.empty()?'#':stack.pop();
                //如果2个不相等,直接返回false;
                if (!topElement.equals(map.get(c))) {
                    return false;
                }
            } else {
                //说明是左括号.入栈
                stack.push(c);
            }
        }
        //最后需要判断栈为空,说明完全匹配,否则就说明有多余的左括号
        return stack.empty();
    }
    public static void main(String[] args) {
        String s="{{{{[]()}}}}";
        System.out.println(isValid2(s));
    }
}
